#include <bits/stdc++.h>

using namespace std;

// 最后一块石头的重量 II
// 有一堆石头，用整数数组 stones 表示
// 其中 stones[i] 表示第 i 块石头的重量。
// 每一回合，从中选出任意两块石头，然后将它们一起粉碎
// 假设石头的重量分别为 x 和 y，且 x <= y
// 那么粉碎的可能结果如下：
// 如果 x == y，那么两块石头都会被完全粉碎；
// 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x
// 最后，最多只会剩下一块 石头，返回此石头 最小的可能重量
// 如果没有石头剩下，就返回 0
// 测试链接 : https://leetcode.cn/problems/last-stone-weight-ii/

// 如果不考虑「有放回」的操作的话，我们可以划分为两个石子堆（正号堆/负号堆）
// 将每次操作中「重量较大」的石子放到「正号堆」，代表在这次操作中该石子重量在「最终运算结果」中应用 + 运算符
// 将每次操作中「重量较少/相等」的石子放到「负号堆」，代表在这次操作中该石子重量在「最终运算结果」中应用 − 运算符
// 这意味我们最终得到的结果，可以为原来 stones 数组中的数字添加 +/− 符号，所形成的「计算表达式」所表示。

// 那有放回的石子重量如何考虑？
// 其实所谓的「有放回」操作，只是触发调整「某个原有石子」所在「哪个堆」中，并不会真正意义上的产生「新的石子重量」。

// 什么意思呢？
// 假设有起始石子 a 和 b，且两者重量关系为 a ≥ b，那么首先会将 a 放入「正号堆」，将 b 放
// 入「负号堆」。重放回操作可以看作产生一个新的重量为 a − b 的“虚拟石子”，将来这个“虚拟
// 石子”也会参与某次合并操作，也会被添加 +/− 符号：
// 当对“虚拟石子”添加 + 符号，即可 +(a − b)，展开后为 a − b，即起始石子 a 和 b 所在「石子堆」不变
// 当对“虚拟石子”添加 − 符号，即可 −(a − b)，展开后为 b − a，即起始石子 a 和 b 所在「石子堆」交换
// 因此所谓不断「合并」&「重放」，本质只是在构造一个折叠的计算表达式，最终都能展开扁平化为非折叠的计算表达式。
// 综上，即使是包含「有放回」操作，最终的结果仍然可以使用「为原来 stones 数组中的数字添加 +/− 符号，形成的“计算表达式”」所表示。

class Solution 
{
public:
    int lastStoneWeightII(vector<int>& stones) 
    {
        int n = stones.size();
        int sum = accumulate(stones.begin(), stones.end(), 0);
        int target = sum / 2;
        // nums中随意选择数字
		// 累加和一定要 <= sum / 2
		// 又尽量接近
        // 非负数组nums中，子序列累加和不超过t，但是最接近t的累加和是多少
	    // 01背包问题(子集累加和尽量接近t) + 空间压缩
        int dp[target + 1];
        memset(dp, 0, sizeof dp);
        for(int i = 0; i < n; ++i)
        {
            for(int j = target; j >= stones[i]; --j)
            {
                // dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]]+nums[i])
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - 2 * dp[target];
    }
};